package com.github.hgkmail.hello.leetcode101.dp.oned;

import java.util.Arrays;

//暴力法：把3个元素的子数列全部枚举出来，判断是否等差数列
//子问题转化：如果num[i]-num[i-1]=num[i-1]-num[i-2]，那么dp[i]=dp[i-1]+1，否则以第i位结尾(必须包含第i位)的子数组没有等差数列
//切入口：以第i位结尾，必须包含第i位的子数组
public class LC413ArithmeticSlices {
    public int numberOfArithmeticSlices(int[] nums) {
        int len=nums.length;
        if (len<3) {
            return 0;
        }
        //dp array 和 default value
        int[] dp=new int[len-2];
        int k=0;
        Arrays.fill(dp, 0);
        //equation方程
        for (int i = 2; i < nums.length; i++) {
            k=i-2;
            if (nums[i]-nums[i-1]==nums[i-1]-nums[i-2]) {
                if (i==2) {
                    dp[k]=1;
                } else {
                    dp[k]=dp[k-1]+1;
                }
            }
        }
        //累加起来
        return Arrays.stream(dp).sum();
    }

    public static void main(String[] args) {
        System.out.println(new LC413ArithmeticSlices().numberOfArithmeticSlices(new int[]{1,2,3,4}));
    }
}
